import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class leetcode_剑指OfferII098_路径的数目 {
    public static void main(String[] args) {
        Solution17 solution17 = new Solution17();
        System.out.println(solution17.uniquePaths(3, 7));
    }
}


class Solution17 {
    // 深度搜索方法，But，超时了
    public int uniquePaths11111(int m, int n) {
        Stack<int[]> stack = new Stack<>();
        int[] start = new int[]{0, 0};
        stack.push(start);
        int ans = 0;
        while (!stack.isEmpty()) {
            int[] mn = stack.pop();
            int x = mn[0], y = mn[1];
            System.out.printf("%s", Arrays.toString(mn));
            if (x == m - 1 && y == n - 1) {
                ans += 1;
                System.out.println();
            }
            int[][] next = {{x + 1, y}, {x, y + 1}};
            for (int[] i : next) {
                if (i[0] >= 0 && i[0] < m && i[1] >= 0 && i[1] < n) {
                    stack.push(i);
                }
            }
        }
        return ans;
    }

    // 动态规划
    public int uniquePaths(int m, int n) {
        // 如果只有1行活一列  永远都只有一种方法
        if (m == 1 || n == 1) {
            return 1;
        }
        int[][] dp = new int[m][n];
        dp[0][1] = 1;
        dp[1][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 如果时到达第一行或者第一列的任何地方，都只有一种方法
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
//        Arrays.stream(dp).forEach(p -> System.out.println(Arrays.toString(p)));
        return dp[m-1][n-1];
    }
}